The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP). Note, nothing described or referenced in this document is admitted as prior art to this application unless explicitly so stated.
Two general approaches to address the problem of fair bandwidth partitioning used in the industry are Distributed Round Robin (DRR) and Weighted Random Early Detection (WRED). WRED is described in Lin et al., U.S. Pat. No. 6,463,068, issued Oct. 8, 2002, which is hereby incorporated by reference in its entirety.
DRR stores traffic from different classes into separate queues and serves these queues in a round-robin fashion. DRR can provide quantum-level fairness; however, it is rather complex to implement, and such implementations are not easily scalable nor expandable to be able to service additional resources (e.g., the expanding number of queues). WRED, on the other hand, is much simpler to implement, as it stores packets into one single FIFO buffer. Unfortunately, it offers only limited fairness and it is hard to set WRED's parameters, which are not self-adjusting to address changing traffic conditions. Even though many implementations involve adopting WRED on individual queues of DRR, the task of bandwidth partitioning is still mainly done by DRR because of the unsatisfactory performance of WRED.
Another recently developed approach is Approximate Fair Dropping (AFD), which is described in Pan et al., “Approximate Fairness through Differential Dropping,” ACM SIGCOMM Computer Communication Review, Vol. 33, Issue 2 (April 2003), pp. 23-39, and is hereby incorporated by reference in its entirety. AFD provides fair bandwidth allocation to multiple flows of packets entering a single queue, where a flow is defined as a stream of packets with the same source-destination addresses, although other definitions of flows could be used. AFD bases its packet dropping decisions on a recent history of packet arrivals for these packet flows, and can approximate maximum-minimum fairness with a limited amount of additional states.
Briefly, the high-level design of AFD has three key elements of arrival rate estimation, drop probability calculation, and fair share calculation. In regards to arrival rate estimation, AFD keeps track of all packets that have recently arrived at the entrance to the physical queue over a certain time period. That is, for each packet flow i, let mi be the amount of traffic (i.e., number of all packets arrived, not just those admitted) for the flow i. In determining whether or not a particular packet is dropped or admitted to the queue, AFD uses the following equation to admit or drop arriving packets for flow i fairly, find di such that mi*(1−di)=mfair. In other words, di=(1−mi/mfair); and if di is positive, drop the incoming packet with probability di; otherwise, admit packet to the queue. The fair share is estimated dynamically as follows by looking at the size of the queue: mfair=mfair−a1*(Qlen−Qref)+a2*(Qlen—old−Qref), where Qlen is the real queue length (currently measured); Qlen—old is the real queue length (previously measured); Qref is the reference queue length (set by the operator); a1 and a2 are the averaging parameters (design parameters). Note, Qlen and Qlen—old together give both the first and second moment information about the queue size; that is, not only how the current occupancy of the queue, but also whether it is going towards the target occupancy or moving away from the target occupancy, which helps us control mfair more accurately. AFD provides a nice theoretical basis for performing bandwidth partitioning; but does not provide a comprehensive and practically implementable solution.